package com.atcumt.Carl.Dp;

public class Dp03 {

    /**
     * 打家劫舍
     */
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        if (n == 0 || nums == null) {
            return 0;
        }

        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[n - 1]; // 0~n-1房屋偷的最大金额数
    }

    /**
     * 打家劫舍Ⅱ：首尾相连
     */
    public int rob2(int[] nums) {
        int len = nums.length - 1;
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 0) {
            return 0;
        }

        int rob1 = robHelper(nums, 0, len - 1);
        int rob2 = robHelper(nums, 1, len);
        return Math.max(rob1, rob2);
    }

    private int robHelper(int[] nums, int start, int end) {
        if (start == end) {
            return nums[start];
        }
        int n = nums.length;
        int[] dp = new int[n];
        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[end];
    }
}
